package com.jiang.daily.Q63;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/02/08 23:18
 */
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n]; // 表示每一行的路径
        dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) { // 如果当前为1， 表示走不通，设置dp[j]为0
                    dp[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) { // 如果左边一个位置走的通
                    dp[j] += dp[j - 1]; // 上边的值dp[j] + 左边的值dp[j - 1]，给到当前dp[j]
                    // 即使走不通，dp[j]保留上边的值
                }
            }
        }
        return dp[n - 1];
    }
}
